// https://www.lintcode.com/problem/maximal-rectangle/description

class Solution {
public:
    /**
     * @param matrix: a boolean 2D matrix
     * @return: an integer
     */
    //法一：单调栈
    class Solution {
    public:
        int maximalRectangle(vector<vector<char>>& matrix) {
            int res = 0;
            if (matrix.empty()) return res;
            int m = matrix.size();
            int n = matrix[0].size();
            vector<vector<int>> rec(m, vector<int>(n + 1, 0));
            for (int i = 0; i < m; ++i) {
                stack<int> s;
                for (int j = 0; j <= n; ++j) {
                    if (j < n && matrix[i][j] == '1') {
                        rec[i][j] = (i == 0 ? 0: rec[i - 1][j]) + 1;
                    }
                    while (!s.empty() && rec[i][s.top()] >= rec[i][j]) {
                        int tmp = s.top();
                        s.pop();
                        int height = rec[i][tmp];
                        int l = s.empty()?0:(s.top() + 1);
                        int r = j - 1;
                        res = max(res, (r - l + 1) * height);
                    }
                    s.push(j);
                }
            }
            return res;
        }
    };


    // int maximalRectangle(vector<vector<bool>> &matrix) {
    //     if (matrix.empty())
    //         return 0;
    //     int n = matrix.size();
    //     int m = matrix[0].size();
    //     vector<vector<int>> rec(n, vector<int>(m + 1));
    //     int res = 0;
    //     for (int i = 0; i < n; ++i) {
    //         stack<int> stack;
    //         for (int j = 0; j <= m; ++j) {
    //             if (j == m || matrix[i][j] == 0) {
    //                 rec[i][j] = 0;
    //             } else {
    //                 rec[i][j] = 1;
    //                 if (i > 0) {
    //                     rec[i][j] += rec[i - 1][j];
    //                 }  
    //             }
    //             while (!stack.empty() && rec[i][j] <= rec[i][stack.top()]) {
    //                 int h = rec[i][stack.top()];
    //                 stack.pop();
    //                 // int l = stack.top() + 1;
    //                 int l = stack.empty() ? 0 : (stack.top() + 1);
    //                 int r = j - 1;
    //                 res = max(res, (r - l + 1) * h);
    //             }
    //             stack.push(j);
    //         }
    //     }
    //     return res;
    // }
    
    //法二：DP
    // int maximalRectangle(vector<vector<bool>> &matrix) {
    //     if (matrix.empty())
    //         return 0;
    //     int n = matrix.size();
    //     int m = matrix[0].size();
    //     vector<vector<int>> up(n, vector<int>(m));
    //     vector<vector<int>> left(n, vector<int>(m));
    //     vector<vector<int>> right(n, vector<int>(m));
    //     int res = 0;
    //     for (int i = 0; i < n; ++i) {
    //         for (int j = 0; j < m; ++j) {
    //             if (!matrix[i][j]) {
    //                 up[i][j] = 0;
    //             } else {
    //                 up[i][j] = 1;
    //                 if (i > 0) {
    //                     up[i][j] += up[i - 1][j];
    //                 }
    //             }
    //         }
    //         int l = 0;
    //         for (int j = 0; j < m; ++j) {
    //             if (!matrix[i][j]) {
    //                 l = 0;
    //                 left[i][j] = 0;
    //             } else {
    //                 ++l; //要重新记，不好用前面的做dp
    //                 left[i][j] = l;
    //                 if (i > 0 && matrix[i - 1][j] && left[i - 1][j] < left[i][j]) { 
    //                     //重要，如果上面的边短，就更新成上面的
    //                     left[i][j] = left[i - 1][j];
    //                 }
    //             }
    //         }
    //         int r = 0;
    //         for (int j = m - 1; j >= 0; --j) {
    //             if (!matrix[i][j]) {
    //                 r = 0;
    //                 right[i][j] = 0;
    //             } else {
    //                 ++r;
    //                 right[i][j] = r;
    //                 if (i > 0 && matrix[i - 1][j] && right[i - 1][j] < right[i][j]) {
    //                     right[i][j] = right[i - 1][j];
    //                 }
    //             }
    //         }
    //     }
    //     for (int i = 0; i < n; ++i) {
    //         for (int j = 0; j < m; ++j) {
    //             res = max(res, up[i][j] * (left[i][j] + right[i][j] - 1));
    //         }
    //     }
    //     return res;
    // }
};